package com.sise.Array;

/**
 *      287. 寻找重复数
 *
 *      给定一个包含n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
 *      假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
 *      你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
 *
 *      输入：nums = [1,3,4,2,2]
 *      输出：2
 *
 *      题解：
 *      https://leetcode-cn.com/problems/find-the-duplicate-number/solution/287xun-zhao-zhong-fu-shu-by-kirsche/
 *
 *      这里使用的是 快慢指针，同时作用的是映射
 *      如果数组中有重复的数，以数组 [1,3,4,2,2] 为例,我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n)，
 *      其映射关系 n->f(n) 为：
 *      0->1
 *      1->3
 *      2->4
 *      3->2
 *      4->2
 *
 *      同样的，我们从下标为 0 出发，根据 f(n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推产生一个类似链表一样的序列。
 *      0->1->3->2->4->2->4->2->4->2……
 *
 *      从理论上讲，数组中如果有重复的数，那么就会产生多对一的映射，这样，形成的链表就一定会有环路了，
 *
 *      综上
 *      1.数组中有一个重复的整数 <==> 链表中存在环
 *      2.找到数组中的重复整数 <==> 找到链表的环入口
 *
 *
 *
 */
public class _287_findDuplicate {
    public int findDuplicate(int[] nums) {

        int slow = 0;
        int fast = 0;
        slow = nums[slow];          // 由于使用的快慢指针本质是 映射，故此这里用的是 num[] 值
        fast = nums[nums[fast]];    // 快指针需嵌套双层 num[]
        while (slow != fast){       // 当快慢指针相遇时就停下来
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        /**
         *  假设起点：0
         *  环开始的地方：x
         *  相遇点：y
         *
         *  慢指针：0->x->y
         *  快指针：0->x->y->x->y (这里可能 fast 已经走了很多圈 x->y)
         *
         *  故此 2*(x+y) = x+y+(y->x的距离)+y    =>  x = y->x的距离
         *
         *  low = fast 时，快慢指针相遇，low 走过的距离是初始点（0）到环状开始的点 （x） 加上 环状开始的点（x） 到相遇点（y） 这段距离，
         *  而fast走过的距离是 初始点（0）到环状开始的点（x），点（x） 到点（y），点（y）到点（x），点（x）到点（y）。又因为fast走过的距离是low的两倍，
         *  设0到x长度为a，x到y长度为b,则有2*（a+b） = a+ b+ (y到x的距离) + b，则y到x的距离就等于0到x的距离。
         *  所以当新的两个指针 一个从0出发，一个从相遇点y出发时，他们走到的相同的值就是环状开始的点，即x点。
         */
        int pre1 = 0;
        int pre2 = slow;
        while (pre1 != pre2){
            pre1 = nums[pre1];
            pre2 = nums[pre2];
        }
        return pre1;
    }
}
